# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        """超时"""
        if not head:
            return head
        flag = True
        while flag:
            flag, now_note = False, head
            while now_note.next:
                if now_note.val > now_note.next.val:
                    now_note.val, now_note.next.val = now_note.next.val, now_note.val
                    flag = True
                now_note = now_note.next
        return head


class Solution2:
    def sortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        mid_list, now_note = [], head
        while now_note:
            mid_list.append(now_note.val)
            now_note = now_note.next
        mid_list.sort()
        now_note = head
        for num in mid_list:
            now_note.val = num
            now_note = now_note.next
        return head